package merge_sort

//MergeSortRecurs 归并排序
//时间复杂度 平均：O(nlogn) 最坏：O(nlogn) 最好：O(n)
//空间复杂度 O(n)
//稳定的排序
//递归实现
func MergeSortRecurs(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	mid := ln/2
	left := MergeSortRecurs(nums[:mid])
	right := MergeSortRecurs(nums[mid:])
	
	ret := []int{}
	llen := len(left)
	rlen := len(right)
	i,j := 0,0; 

	for i < llen && j < rlen {
		if left[i] <= right[j] {
			ret = append(ret, left[i])
			i++
		} else {
			ret = append(ret, right[j])
			j++
		}
	}
	if i < llen {
		ret = append(ret, left[i:]...)
	}
	if j < rlen {
		ret = append(ret, right[j:]...)
	}
	return ret
}